{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #库存管理 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #divide-and-conquer #quickselect #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #分治 #快速选择 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: inventoryManagement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #库存管理 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>仓库管理员以数组 <code>stock</code> 形式记录商品库存表，其中 <code>stock[i]</code> 表示对应商品库存余量。请返回库存余量最少的 <code>cnt</code> 个商品余量，返回&nbsp;<strong>顺序不限</strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stock = [2,5,7,4], cnt = 1\n",
    "<strong>输出：</strong>[2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stock = [0,2,3,6], cnt = 2\n",
    "<strong>输出：</strong>[0,2] 或 [2,0]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= cnt &lt;= stock.length &lt;= 10000<br />\n",
    "\t0 &lt;= stock[i] &lt;= 10000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [zui-xiao-de-kge-shu-lcof](https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [zui-xiao-de-kge-shu-lcof](https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,5,7,4]\\n1', '[0,2,3,6]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        stock.sort()\n",
    "        return stock[:cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        stock.sort()\n",
    "        return stock[:cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        if cnt == 0:\n",
    "            return []\n",
    "        left, right, target = 0, len(stock) - 1, cnt - 1\n",
    "        def partition(left: int, right: int) -> int:\n",
    "            randomIdx = random.randint(left, right)\n",
    "            stock[randomIdx], stock[left] = stock[left], stock[randomIdx]\n",
    "            pivot, j = stock[left], left\n",
    "            for i in range(left + 1, right + 1):\n",
    "                if stock[i] <= pivot:\n",
    "                    j += 1\n",
    "                    stock[i], stock[j] = stock[j], stock[i]\n",
    "            stock[j], stock[left] = stock[left], stock[j]\n",
    "            return j\n",
    "        while True:\n",
    "            idx = partition(left, right)\n",
    "            if idx == target:\n",
    "                return stock[:cnt]\n",
    "            elif idx < target:\n",
    "                left = idx + 1\n",
    "            else:\n",
    "                right = idx - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        stock.sort()\n",
    "        return stock[:cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        # 使用堆\n",
    "        hq=heapify(stock)\n",
    "        result=[]\n",
    "        for i in range(cnt):\n",
    "            result.append(heappop(stock))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        stock.sort()\n",
    "        ans = []\n",
    "        for i in range(cnt):\n",
    "            ans.append(stock[i])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heapify(self, nums, idx, end):\n",
    "        while idx * 2 + 1 <= end:\n",
    "            left = idx * 2 + 1\n",
    "            right = idx * 2 + 2\n",
    "            if right > end:\n",
    "                larger = left\n",
    "            else:\n",
    "                if nums[left] > nums[right]:\n",
    "                    larger = left\n",
    "                else:\n",
    "                    larger = right\n",
    "            if nums[larger] > nums[idx]:\n",
    "                nums[larger], nums[idx] = nums[idx], nums[larger]\n",
    "                idx = larger\n",
    "            else:\n",
    "                break\n",
    "\n",
    "    # 维护一个k容量的大顶堆\n",
    "    def buildMaxHeap(self, nums, k):\n",
    "        for i in range((k - 2) // 2, -1, -1):\n",
    "            self.heapify(nums, i, k - 1)\n",
    "\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        self.buildMaxHeap(stock, cnt)\n",
    "        print(stock)\n",
    "        for i in range(cnt, len(stock)):\n",
    "            if stock[i] < stock[0]:\n",
    "                stock[i], stock[0] = stock[0], stock[i]\n",
    "                self.heapify(stock, 0, cnt - 1)\n",
    "        return stock[:cnt]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        stock.sort()\n",
    "        res = []\n",
    "        for i in range(cnt):\n",
    "            res.append(stock[i])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        sort_stock=sorted(stock)\n",
    "        ans=sort_stock[:cnt]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        import heapq\n",
    "        heapq.heapify(stock)\n",
    "        smallest = []\n",
    "        for i in range(cnt):\n",
    "            smallest.append(heapq.heappop(stock))\n",
    "        return smallest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        if len(stock)==0 or cnt==0:\n",
    "            return []\n",
    "        i=0\n",
    "        j=len(stock)-1\n",
    "        self.participate(stock,i,j)\n",
    "        return stock[:cnt]\n",
    "        \n",
    "    def participate(self, stock,i,j):\n",
    "        if i>j:\n",
    "            return \n",
    "        m=self.quick(stock,i,j)\n",
    "        self.participate(stock,i,m-1)\n",
    "        self.participate(stock,m+1,j)\n",
    "    def quick(self, stock,i,j):\n",
    "        flag=stock[i]\n",
    "        while i<j:\n",
    "            while i<j and stock[j]>=flag:\n",
    "                j-=1\n",
    "            stock[i]=stock[j]\n",
    "            while i<j and stock[i]<=flag:\n",
    "                i+=1\n",
    "            stock[j]=stock[i]\n",
    "        stock[j]=flag\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        list1=[0]*10001\n",
    "        ans=[]\n",
    "        for i in stock:\n",
    "            list1[i]+=1\n",
    "        for i in range(10001):\n",
    "            if list1[i]>0 and cnt>0:\n",
    "                while list1[i]>0:\n",
    "                    if cnt==0:\n",
    "                        break\n",
    "                    ans.append(i)\n",
    "                    cnt-=1\n",
    "                    list1[i]-=1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        if len(stock) == 0 or cnt == 0:\n",
    "            return []\n",
    "        if cnt >= len(stock):\n",
    "            return stock\n",
    "        res = []\n",
    "        heapq.heapify(stock)\n",
    "        while cnt:\n",
    "            res.append(heapq.heappop(stock))\n",
    "            cnt -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        stock = sorted(stock)\n",
    "        l1 = []\n",
    "        for i in range(cnt):\n",
    "            l1.append(stock[i])\n",
    "        return l1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        import heapq\n",
    "        queue = []\n",
    "        if cnt == 0:\n",
    "            return []\n",
    "        while stock:\n",
    "            if len(queue) < cnt:\n",
    "                heapq.heappush(queue, -1 * stock.pop())\n",
    "            else:\n",
    "                heapq.heappop(queue)\n",
    "                heapq.heappush(queue, -1 * stock.pop())\n",
    "        return [-i for i in queue]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        heap = []\n",
    "        n = len(stock)\n",
    "        for i in range(cnt):\n",
    "            heap.append(-stock[i])\n",
    "        heapq.heapify(heap)\n",
    "        if not heap:\n",
    "            return []\n",
    "        for i in range(cnt, n):\n",
    "\n",
    "            if -stock[i] >= heap[0]:\n",
    "                heapq.heapreplace(heap, -stock[i])\n",
    "        return [-_ for _ in heap]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        if cnt==0: return []\n",
    "        heap = [-x for x in stock[:cnt]]\n",
    "        heapq.heapify(heap)\n",
    "        for num in stock[cnt:]:\n",
    "            if num < -heap[0]:\n",
    "                heapq.heapreplace(heap, -num)\n",
    "        return [-x for x in heap]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        def mergesort(arr):\n",
    "            if len(arr) < 2:\n",
    "                return arr\n",
    "            mid = len(arr) // 2\n",
    "            return merge(mergesort(arr[:mid]), mergesort(arr[mid:]))\n",
    "            \n",
    "\n",
    "        def merge(l, r):\n",
    "            res = []\n",
    "            i, j = 0, 0\n",
    "            while i < len(l) and j < len(r):\n",
    "                if l[i] < r[j]:\n",
    "                    res.append(l[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    res.append(r[j])\n",
    "                    j += 1\n",
    "            res.extend(l[i:])\n",
    "            res.extend(r[j:])\n",
    "            return res\n",
    "        stock = mergesort(stock)\n",
    "        \n",
    "        return stock[:cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        if cnt == 0: return []\n",
    "        heap = [-x for x in stock[:cnt]]\n",
    "        heapq.heapify(heap)\n",
    "\n",
    "        for num in stock[cnt:]:\n",
    "            if num < -heap[0]:\n",
    "                heapq.heapreplace(heap, -num)\n",
    "        \n",
    "        return [-x for x in heap]\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        if cnt == 0:\n",
    "            return []\n",
    "        n = len(stock)\n",
    "        hp = [-stock[i] for i in range(cnt)]\n",
    "        heapq.heapify(hp)\n",
    "        for i in range(cnt, n):\n",
    "            if -hp[0] > stock[i]:\n",
    "                heapq.heappop(hp)\n",
    "                heapq.heappush(hp, -stock[i])\n",
    "        hp = [-hp[i] for i in range(cnt)]\n",
    "        return hp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        if cnt == 0:\n",
    "            return []\n",
    "        heap = []\n",
    "        for i in range(cnt):\n",
    "            heapq.heappush(heap, -stock[i])\n",
    "\n",
    "        for i in range(cnt, len(stock)):\n",
    "            if -stock[i] > heap[0]:\n",
    "                heapq.heapreplace(heap, -stock[i])\n",
    "        \n",
    "        return [-i for i in heap]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        if not cnt: return []\n",
    "        heap = [-x for x in stock[:cnt]]\n",
    "        heapq.heapify(heap)\n",
    "        for num in stock[cnt:]:\n",
    "            if num < -heap[0]:\n",
    "                heapq.heappop(heap)\n",
    "                heapq.heappush(heap, -num)\n",
    "        return [-x for x in heap]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        if cnt == 0: return []\n",
    "        heap = [-x for x in stock[:cnt]]\n",
    "        heapq.heapify(heap)\n",
    "        for num in stock[cnt:]:\n",
    "            if num < -heap[0]:\n",
    "                heapq.heapreplace(heap, -num)\n",
    "        return [-x for x in heap]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        if cnt == 0: return []\n",
    "        # python中只有最小堆没有最大堆\n",
    "        # 因此可以对list取负来获得最大堆\n",
    "        heap = [-x for x in stock[:cnt]]\n",
    "        heapq.heapify(heap)\n",
    "        for num in stock[cnt:]:\n",
    "            if num < -heap[0]: \n",
    "                heapq.heapreplace(heap, -num)\n",
    "        return [-x for x in heap] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        return heapq.nsmallest(cnt, stock)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        #法1 排序\n",
    "        \"\"\"\n",
    "        stock.sort()\n",
    "        ans = []\n",
    "        #下面这段代码可以被简化为 stock[:cnt]\n",
    "        for i in range(cnt):\n",
    "            ans.append(stock[i])\n",
    "        return ans\n",
    "        \"\"\"\n",
    "\n",
    "        #法2 堆 始终维护数组的前cnt小值\n",
    "        if cnt == 0: return list()\n",
    "\n",
    "        hp = [-x for x in stock[:cnt]] #python中的堆为小根堆，因此要对数组中的数取相反数\n",
    "\n",
    "        heapq.heapify(hp)\n",
    "        for i in range(cnt, len(stock)):\n",
    "            if -hp[0] > stock[i]:\n",
    "                heapq.heappop(hp)\n",
    "                heapq.heappush(hp, -stock[i])\n",
    "        ans = [-x for x in hp]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, arr: List[int], k: int) -> List[int]:\n",
    "        heap = [-num for num in arr[:k]]\n",
    "        heapq.heapify(heap)\n",
    "\n",
    "        for i in range(k, len(arr)):\n",
    "            heapq.heappushpop(heap, -arr[i])\n",
    "\n",
    "        return [-i for i in heap]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        return heapq.nsmallest(cnt, stock)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        return nsmallest(cnt, stock)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        v = [(i,j) for i,j in enumerate(stock)]\n",
    "        stock.sort()\n",
    "        return stock[:cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "\n",
    "# # 该方法结果对，但是利用了内置函数\n",
    "# class Solution:\n",
    "#     def inventoryManagement(self, arr: List[int], k: int) -> List[int]:\n",
    "#         arr.sort()\n",
    "#         return arr[0: k]\n",
    "\n",
    "# # 快速排序\n",
    "# class Solution:\n",
    "#     def inventoryMangement(self, arr: List[int], k: int) -> List[int]:\n",
    "#         def quick_sort(arr, left, right):\n",
    "#             if left >= right: return  #换成return arr速度更慢\n",
    "#             i, j = left, right\n",
    "#             while i < j:\n",
    "#                 while i < j and arr[j] >= arr[left]: j -= 1 #从右向左找小于索引的值\n",
    "#                 while i < j and arr[i] <= arr[left]: i += 1 #从左向右找大于索引的值\n",
    "#                 arr[i], arr[j] = arr[j], arr[i]\n",
    "#             arr[i], arr[left] = arr[left], arr[i]\n",
    "#             #递归处理子数组\n",
    "#             quick_sort(arr, left, i - 1)\n",
    "#             quick_sort(arr, i + 1, right)\n",
    "\n",
    "#         quick_sort(arr, 0, len(arr) - 1)\n",
    "#         return arr[: k]\n",
    "\n",
    "\n",
    "# 基于快速排序的数组划分，只需要将数组划分为最小的k个数和其他数字两部分即可\n",
    "class Solution:\n",
    "    def inventoryManagement(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k >= len(arr): return arr\n",
    "        def quick_sort(l, r):\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while i < j and arr[j] >= arr[l]: j -= 1\n",
    "                while i < j and arr[i] <= arr[l]: i += 1\n",
    "                arr[i], arr[j] = arr[j], arr[i]\n",
    "            arr[l], arr[i] = arr[i], arr[l]\n",
    "            if k < i: return quick_sort(l, i - 1)\n",
    "            if k > i: return quick_sort(i + 1, r)\n",
    "            return arr[: k]\n",
    "        return quick_sort(0, len(arr) - 1)\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        if cnt >= len(stock): return stock\n",
    "        def quick_select(l, r):\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while i < j and stock[j] >= stock[l]: j -= 1\n",
    "                while i < j and stock[i] <= stock[l]: i += 1\n",
    "                stock[i], stock[j] = stock[j], stock[i]\n",
    "            stock[l], stock[i] = stock[i], stock[l]\n",
    "            if cnt < i: return quick_select(l, i - 1)\n",
    "            if cnt > i: return quick_select(i + 1, r)\n",
    "            return stock[:cnt]\n",
    "        return quick_select(0, len(stock) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        if cnt == 0: return []\n",
    "        if cnt >= len(stock): return stock\n",
    "        def quick_sort(l, r):\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while i < j and stock[j] >= stock[l]:\n",
    "                    j -= 1\n",
    "                while i < j and stock[i] <= stock[l]:\n",
    "                    i += 1\n",
    "                stock[i], stock[j] = stock[j], stock[i]\n",
    "            stock[l], stock[i] = stock[i], stock[l]\n",
    "            if cnt < i: return quick_sort(l, i-1)\n",
    "            if cnt > i: return quick_sort(i+1, r)\n",
    "            return stock[:cnt]\n",
    "        return quick_sort(0, len(stock) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        if cnt >= len(stock): return stock\n",
    "        def quick_sort(l, r):\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while i < j and stock[j] >= stock[l]: j -= 1\n",
    "                while i < j and stock[i] <= stock[l]: i += 1\n",
    "                stock[i], stock[j] = stock[j], stock[i]\n",
    "            stock[l], stock[i] = stock[i], stock[l]\n",
    "            if cnt < i: return quick_sort(l, i - 1) \n",
    "            if cnt > i: return quick_sort(i + 1, r)\n",
    "            return stock[:cnt]\n",
    "            \n",
    "        return quick_sort(0, len(stock) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        def quick_sort(l,r):\n",
    "            i,j=l,r\n",
    "            if l>=r:\n",
    "                return \n",
    "            while i<j:\n",
    "                while stock[j]>=stock[l] and i<j:\n",
    "                    j-=1\n",
    "                while stock[i]<=stock[l] and i<j:\n",
    "                    i+=1\n",
    "                stock[i],stock[j]=stock[j],stock[i]\n",
    "            stock[i],stock[l]=stock[l],stock[i]\n",
    "            quick_sort(l,i-1)\n",
    "            quick_sort(i+1,r)\n",
    "        quick_sort(0,len(stock)-1)\n",
    "        return stock[:cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        def partition(left,right):\n",
    "            p = stock[right]\n",
    "            wall = left - 1\n",
    "            for i in range(left,right):\n",
    "                if stock[i] <= p:\n",
    "                    wall += 1\n",
    "                    stock[wall],stock[i] = stock[i],stock[wall]\n",
    "            stock[wall+1],stock[right] = stock[right],stock[wall+1]\n",
    "            return wall+1\n",
    "\n",
    "        def quick(left,right,k):\n",
    "            mid = partition(left,right)\n",
    "            if mid - left + 1 > k :\n",
    "                return quick(left,mid-1,k) \n",
    "            elif mid - left + 1 < k:\n",
    "                return quick(mid+1,right,k-(mid-left+1))\n",
    "        if cnt == 0:\n",
    "            return []\n",
    "        quick(0,len(stock)-1,cnt)\n",
    "        \n",
    "        return stock[:cnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:\n",
    "        if cnt >= len(stock): return stock\n",
    "        def helper(lo, hi):\n",
    "            i, j = lo, hi\n",
    "            pivot = lo\n",
    "            while i < j:\n",
    "                while i < j and stock[j] >= stock[pivot]: j -= 1\n",
    "                while i < j and stock[i] <= stock[pivot]: i += 1\n",
    "                stock[i], stock[j] = stock[j], stock[i]\n",
    "            stock[pivot], stock[i] = stock[i], stock[pivot]\n",
    "            if cnt < i: return helper(lo, i-1)\n",
    "            if cnt > i: return helper(i+1, hi)\n",
    "            return stock[:cnt]\n",
    "        \n",
    "        return helper(0, len(stock)-1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
